package com.lili.other;

import java.util.LinkedList;

/**
 * @Auther: 李 力
 * @Date: 2024/8/22
 * @Description: 接雨水:求总容量
 * @version: 1.0
 */
public class LeetCode42 {
    public static int trap(int[] hei) {
        LinkedList<Data> stack = new LinkedList<>();
        int sum = 0;
        for (int i = 0; i < hei.length; i++) {
            Data right = new Data(hei[i], i);
            while (!stack.isEmpty() && stack.peek().height < right.height) {
                Data pop = stack.poll();
                Data left = stack.peek();
                if (left != null) {
                    int w = right.i - left.i - 1;
                    int h = Math.min(left.height, right.height) - pop.height;
                    sum += w * h;
                }
            }
            stack.push(right);
        }
        return sum;
    }

    static class Data {
        int height;
        int i;//索引

        public Data(int height, int i) {
            this.height = height;
            this.i = i;
        }
    }
}
